package leetcode_701_800;

import com.sun.deploy.util.ArrayUtil;

import java.util.*;

public class LeeCode_778 {
    public static void main(String[] args) {
        System.out.println(swimInWater(new int[][]{{10, 12, 4, 6}, {9, 11, 3, 5}, {1, 7, 13, 8}, {2, 0, 15, 14}}));
        int[][] grid = {
                {55, 33, 29, 78, 47, 62, 60, 79, 41, 54},
                {34, 16, 93, 64, 38, 46, 91, 8, 40, 65},
                {22, 74, 12, 70, 28, 80, 90, 32, 6, 45},
                {23, 49, 85, 52, 11, 56, 83, 5, 36, 95},
                {31, 48, 14, 89, 76, 82, 19, 26, 97, 63},
                {0, 75, 9, 77, 2, 51, 94, 7, 71, 99},
                {35, 81, 44, 87, 43, 18, 67, 17, 13, 57},
                {92, 53, 37, 39, 20, 88, 15, 68, 24, 66},
                {27, 69, 84, 3, 72, 10, 61, 30, 50, 58},
                {73, 96, 98, 25, 4, 21, 86, 1, 59, 42}};
        System.out.println(swimInWater(grid));
    }

    private static int swimInWater(int[][] grid) {
        int n = grid.length;
        PriorityQueue<int[]> queue = new PriorityQueue<>(Comparator.comparingInt(o -> o[2]));
        queue.add(new int[]{0, 0, grid[0][0]});
        int[][] vis = new int[n][n];
        vis[0][0] = 1;
        int[][] dirs = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        while (!queue.isEmpty()){
            int[] poll = queue.poll();
            int x = poll[0], y = poll[1];
            vis[x][y] = 1;
            if (x == n - 1 && y == n - 1){
                return poll[2];
            }
            for (int[] dir : dirs) {
                int nx = x + dir[0], ny = y + dir[1];
                if (nx < 0 || nx >= n || ny < 0 || ny >= n || vis[nx][ny] == 1) {
                    continue;
                }
                queue.add(new int[]{nx, ny, Math.max(poll[2], grid[nx][ny])});
            }
        }
        return 0;
    }

//    private static boolean check(int[][] grid, int x, int y) {
//        int n = grid.length, stand = grid[x][y];
//        int[][] vis = new int[n][n];
//        Deque<int[]> queue = new ArrayDeque<>();
//        queue.add(new int[]{x, y});
//        int[][] dirs = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
//        boolean f1 = false, f2 = false;
//        while (!queue.isEmpty()) {
//            int size = queue.size();
//            for (int i = 0; i < size; i++) {
//                int[] pop = queue.pop();
//                int x0 = pop[0], y0 = pop[1];
//                if (x0 == 0 && y0 == 0)
//                    f1 = true;
//                else if (x0 == n - 1 && y0 == n - 1)
//                    f2 = true;
//                vis[x0][y0] = 1;
//                for (int[] dir : dirs) {
//                    int nx = x0 + dir[0], ny = y0 + dir[1];
//                    if (nx < 0 || nx >= n || ny < 0 || ny >= n) {
//                        continue;
//                    }
//                    if (vis[nx][ny] == 1 || grid[nx][ny] > stand)
//                        continue;
//                    queue.offer(new int[]{nx, ny});
//                }
//            }
//        }
//        return f1 && f2;
//    }
}
